By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 22, Issue 1, pp. 1-219

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Implicit $O(1)$ Probe Search

Amos Fiat and Moni Naor

pp. 1-10

BibTeX  Abstract Full Text:  PDF

Maintaining the $3$-Edge-Connected Components of a Graph On-Line

Zvi Galil and Giuseppe F. Italiano

pp. 11-28

BibTeX  Abstract Full Text:  PDF

On the Boundedness of Constant-Time-Maintainable Database Schemes

Héctor J. Hernández and Ke Wang

pp. 29-45

BibTeX  Abstract Full Text:  PDF

Tight Worst-Case Performance Bounds for Next-$k$-Fit Bin Packing

Weizhen Mao

pp. 46-56

BibTeX  Abstract Full Text:  PDF

A Note on the Complexity of a Simple Transportation Problem

Greg N. Frederickson

pp. 57-61

BibTeX  Abstract Full Text:  PDF

A Lower Bound on the Size of Shellsort Sorting Networks

Robert Cypher

pp. 62-71

BibTeX  Abstract Full Text:  PDF

A Note on Poset Geometries

Joel Friedman

pp. 72-78

BibTeX  Abstract Full Text:  PDF

An $O(n)$ Algorithm for Determining the Subregion-Tree Representation of a Rectangular Dissection

Sukhamay Kundu

pp. 79-101

BibTeX  Abstract Full Text:  PDF

Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space

Viliam Geffert

pp. 102-113

BibTeX  Abstract Full Text:  PDF

NV-Sequentiality: A Decidable Condition for Call-by-Need Computations in Term-Rewriting Systems

Michio Oyamaguchi

pp. 114-135

BibTeX  Abstract Full Text:  PDF

${\text{ASPACE}}(o(\log \log n))$ is Regular

Kazuo Iwama

pp. 136-146

BibTeX  Abstract Full Text:  PDF

The Complexity of Malign Measures

Peter Bro Miltersen

pp. 147-156

BibTeX  Abstract Full Text:  PDF

Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for $k$-Vertex Connectivity

Joseph Cheriyan, Ming-Yang Kao, and Ramakrishna Thurimella

pp. 157-174

BibTeX  Abstract Full Text:  PDF

Decomposing Finite-Valued Transducers and Deciding Their Equivalence

Andreas Weber

pp. 175-202

BibTeX  Abstract Full Text:  PDF

One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete

Jan Kratochvíl, Petr Savický, and Zsolt Tuza

pp. 203-210

BibTeX  Abstract Full Text:  PDF

Rounds in Communication Complexity Revisited

Noam Nisan and Avi Wigderson

pp. 211-219

BibTeX  Abstract Full Text:  PDF